Error correction codes, which are for the purpose of correcting error contained in received information or in reconstructed information so that the original information can be decoded correctly, are applied to a variety of systems. For example, error correction codes are applied in cases where data is to be transmitted without error when performing mobile communication, FAX or other data communication, and in cases where data is to be reconstructed without error from a large-capacity storage medium such as a magnetic disk or CD.
Among the available error correction codes, it has been decided to adopt turbo codes (see the specification of U.S. Pat. No. 5,446,747) for standardization in next-generation mobile communications. FIG. 14 is a block diagram of a communication system that includes a turbo encoder and a turbo decoder. Numeral 11 denotes the turbo encoder, which is provided on the data transmitting side, and numeral 12 denotes the turbo decoder, which is provided on the data receiving side. Numeral 13 denotes a data communication path. Further, character u represents transmit information data of length N; xa, xb, xc represent encoded data obtained by encoding the information data u by the turbo encoder 11; ya, yb, yc denote received signals that have been influenced by noise and fading as a result of propagation of the encoded data xa, xb, xc through the communication path 13; and u′ represents results of decoding obtained by decoding the received data ya, yb, yc by the turbo decoder 12. These items of data are as expressed below. It should be noted that decoded results u′ include “results of decisions” and “likelihood”.
Original data: u={u1, u2, u3, . . . , UN}
Encoded data: xa={xa1, xa2, xa3, . . . , xak, . . . , xaN}                : xb={xb1, xb2, xb3, . . . , xbk, . . . , xbN}        : xc={xc1, xc2, xc3, . . . , xck, . . . , xcN}        
Receive data: ya={ya1, ya2, ya3, . . . , yak, . . . , yaN}                : yb={yb1, yb2, yb3, . . . , ybk, . . . , ybN}        : yc={yc1, yc2, yc3, . . . , yck, . . . , ycN}        
The turbo encoder 11 encodes the information data u of information length N and outputs the encoded data xa, xb, xc. The encoded data xa is the information data u per se, the encoded data xb is data obtained by the convolutional encoding of the information data u by an encoder ENC1, and the encoded data xc is data obtained by the interleaving (π) of the information data u and convolutional encoding of the interleaved results xa′ by an encoder ENC2. In other words, a turbo code is obtained by combining two convolutional codes. It should be noted that an interleaved output xa′ differs from the encoded data xa only in terms of its sequence and therefore is not output.
FIG. 15 is a diagram showing the details of the turbo encoder 11. Numerals 11a, 11b denote convolutional encoders (ENC1, ENC2) that are identically constructed, and numeral 11c denotes an interleaving unit (π). The convolutional encoders 11a, 11b, which are adapted to output recursive systematic convolutional codes, are each constructed by connecting two flip-flops FF1, FF2 and three exclusive-OR gates EXOR1˜EXOR3 in the manner illustrated. The flip-flops FF1, FF2 take on four states (00), (01), (10), (1,1). If 0 or 1 is input in each of these states, the states undergo a transition as illustrated in FIG. 16 and the encoder ENC1 outputs xa, xb. In FIG. 16, the left side indicates the state prior to input of receive data, the right side the state after the input, the solid lines the path of the state transition when “0” is input and the dashed lines the path of the state transition when “1” is input, and 00, 11, 10, 01 on the paths indicate the values of the output signals xa, xb. By way of example, if “0” is input in the state 0(00), the output is 00 and the state becomes 0(00); if “1” is input, the output is 11 and the state becomes 1(10).
FIG. 17 is a block diagram of the turbo decoder. Turbo decoding is performed by a first elementary decoder (DEC1) 12a using ya and yb first among the received signals ya, yb, yc. The elementary decoder 12a is a soft-output elementary decoder and outputs the likelihood of decoded results. Next, similar decoding is performed by a second elementary decoder (DEC2) 12b using the likelihood, which is output from the first elementary decoder 12a, and yc. That is, the second elementary decoder 12b also is a soft-output elementary decoder and outputs the likelihood of decoded results. Here yc is a received signal corresponding to xc, which was obtained by interleaving the information data u and encoding the interleaved results. Accordingly, the likelihood that is output from the first elementary decoder 12a is interleaved by an interleaver (π) 12c before it enters the second elementary decoder DEC2.
The likelihood output from the second elementary decoder 12b is deinterleaved by a deinterleaver (π−1) 12d and then is fed back as the input to the first elementary decoder 12a. Further, u′ is decoded data (results of decoding) obtained by rendering a “0”, “1” decision regarding the deinterleaved results from the second elementary decoder 12b. Error rate is reduced by repeating the above-described decoding operation a prescribed number of times.
With turbo decoding, errors in results of decoding decline whenever decoding processing is repeated. However, there are instances where the number of repetitions needed to eliminate errors in decoded results varies depending upon the state of the communication path, etc. As a consequence, if data is decoded correctly with a small number of repetitions, from this point onward the turbo decoder repeats unnecessary decoding operations until a set number of operations is executed.
Further, with turbo decoding, errors in results of decoding decline whenever decoding processing is repeated. However, there are cases where not all errors are corrected and errors remain even though decoding processing is executed the set number of times. In such cases there are instances where error is reduced considerably and if decoding processing is executed one more time, there is a good possibility that all errors will be corrected. With the conventional turbo decoder, decoded results containing error are output as is, without taking the above-mentioned possibility into account, when decoding has been performed the set number of times.
Further in the conventional turbo decoder, the first and second elementary decoders 12a, 12b execute first and second decoding processes with regard to a combination of different received signals. The decoding operations, however, are exactly the same. Accordingly, there is the possibility that one elementary decoder can be used for both the first and second decoding processes. With the prior art, however, the arrangement is such that two, i.e., the first and second, elementary decoders are used for the first and second decoding processes. This results in a large amount of hardware. A problem arises also in terms of power consumption.
As shown in FIG. 17, the output of the turbo decoder is the result of deinterleaving the output of the second elementary decoder 12b. As a result, if errors remain in the decoded data, the errors are randomized by deinterleaving. As shown in (a) of FIG. 18, there are many cases where the units of the turbo code are very long, and in such cases a single unit of turbo code includes a plurality of information blocks. If errors are randomized by deinterleaving in such cases, the errors are dispersed over a plurality of information blocks, as shown at (b) of FIG. 18, the error rate on a per-information-block basis increases and, if resend control is carried out in units of the information blocks, a problem that arises is an increase in number of resends.
Further, in next-generation mobile communications, information transmitted will be a mix of information of various properties and, depending upon the type of data transmitted, there will be instances where it would be better for the error patterns in the decoded data to be bursty and instances where it would be better for the error patterns to be random. With the conventional turbo decoder, however, error patterns contained in the decoded data that is output cannot be make bursty or random as necessary.
Accordingly, an object of the present invention is to so arrange it that if all errors have been corrected before the number of repetitions of decoding attains a set number, the results of decoding are output immediately and the decoding operation is halted.
Another object of the present invention is to so arrange it that when there is a possibility that all errors will be corrected if decoding processing is executed one more time in an instance where all errors have not been not corrected and a prescribed number of errors remain despite the fact that decoding processing has been executed a set number of times, the decoding operation will not be halted and will be executed one more time.
A further object of the present invention is to make it possible to use one elementary decoder for both the first and second decoding processes of the prior art.
Still another object of the present invention is to so arrange it that an error generation pattern contained in decoded data is rendered bursty.
Still another object of the present invention is to so arrange it that an error pattern contained in decoded data to be output can be made bursty or random as necessary.